﻿/************************************************************
*
* 命名空间：Deep.Algorithm.Sorting
* 文件名称：QuickSort.cs
* 创建者：王嘉庆
* 创建日期：2021-05-29 20:39:07
* 邮箱：1101202419@qq.com
* 博客：https://blog.csdn.net/wuxinwudai
* 功能描述：
* 使用说明：
* 最后更新日期：
*************************************************************/
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Deep.Algorithm.Sorting
{
    /// <summary>
    /// 快速排序法，稳定算法，时间复杂度 O(nlogN) 到 O(n^2)
    /// </summary>
    public static class QuickSort
    {
        public static T[] Sort<T>(T[] arr) where T : IComparable
        {
             Sort<T>(arr, 0, arr.Length - 1);
             return arr;
        }

        private  static void Sort<T>(T[] arr, int lo, int hi) where T : IComparable
        {
            if (hi <= lo)
            {
                return;
            }

            int partion = Partion(arr, lo, hi);
            Sort(arr, lo, partion - 1);
            Sort(arr, partion + 1, hi);
        }
        /// <summary>
        /// 分区
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="arr"></param>
        /// <param name="lo"></param>
        /// <param name="hi"></param>
        /// <returns></returns>
        private static int Partion<T>(T[] arr, int lo, int hi) where T : IComparable
        {
            T key = arr[lo];//暂定第一个值为分界值
            int left = lo, right = hi + 1;//定义两个指针，初始指向最小索引和最大索引的下一个位置
            while (true)
            {
                while (key.CompareTo(arr[--hi])< 0)
                {
                    if (right == lo)
                    {
                        break;
                    }
                }
                while (key.CompareTo(arr[++left]) > 0)
                {
                    if (left == lo)
                    {
                        break;
                    }
                }
            }
        }
    }
}
